package 数据结构.章节09;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author 挚爱之夕
 * @date 2021/10/14 - 10 - 14 - 16:42
 * @Description: 数据结构.章节09
 * @Version: 1.0
 */
public class _166_猫狗收容所 {
    public static void main(String[] args) {
        int[][] a = new int[][]{
                {1, 1},
                {1, -1},
                {2, 0},
                {2, -1}
        };
        ArrayList<Integer> ans = ans(a);
        System.out.println(ans);
    }
    private static class Animal{
        int type;
        int time;
        static int timeLine;//时间点

        public Animal(int type) {
            this.type = type;
            this.time = timeLine++;
        }
    }
    private static ArrayList<Integer> ans(int[][] ope){
        ArrayList<Integer> res = new ArrayList<>();
        Queue<Animal> cats = new LinkedList<>();
        Queue<Animal> dogs = new LinkedList<>();
        for(int[] row:ope){
            int op = row[0];
            int typeNumber = row[1];
            if(op == 1){    //增加
                if(typeNumber > 0){
                    dogs.add(new Animal(typeNumber));
                }
                if(typeNumber < 0){
                    cats.add(new Animal(typeNumber));
                }
            }else if(op == 2){  //减少
                if(typeNumber == 0){    //取两个队列中timeline最小的
                    if((!dogs.isEmpty()) &&(cats.isEmpty() || dogs.peek().time < cats.peek().time )){
                        res.add(dogs.poll().type);
                    }
                    if((!cats.isEmpty())&&(dogs.isEmpty() || dogs.peek().time > cats.peek().time)){
                        res.add(cats.poll().type);
                    }
                }else{
                    if(typeNumber == 1 && !dogs.isEmpty()){
                        res.add(dogs.poll().type);
                    }
                    if(typeNumber == -1 && !cats.isEmpty()){
                        res.add(cats.poll().type);
                    }
                }
            }else{
                break;
            }
        }
        return res;
    }
}

